package main.java.leetcode.简单;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class leetcode118_杨辉三角 {

    @Test
    public void test(){
        List<List<Integer>> generate = generate(15);
        for (List<Integer> num : generate){
            for (Integer n:num){
                System.out.print(n+" ");
            }
            System.out.println();
        }
    }

    /**
     * 输入: numRows = 5
     * 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
     * 每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第 nn 行的第 ii 个数等于第 n-1n−1 行的第 i-1i−1 个数和第 ii 个数之和。
     * 这也是组合数的性质之一，
     * 即 \mathcal{C}_n^i=\mathcal{C}_{n-1}^i+\mathcal{C}_{n-1}^{i-1}C
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i = 0;i<numRows;i++){
            ArrayList<Integer> integers = new ArrayList<>();
            for (int j = 0;j<=i;j++){
                if (j==0||j==i){
                    integers.add(1);
                }else if(i!=0){
                    integers.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
                }
            }
            list.add(integers);
        }
        return list;
    }
}
